"""
给定一个可包含重复数字的序列，返回所有不重复的全排列。
示例:
输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]
"""
class Solution:
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.res = set()
        def perm(s, p, q):
            if p == len(s):
                self.res.add(tuple(s[:]))
            else:
                for i in range(p, q + 1):
                    s[i], s[p] = s[p], s[i]
                    perm(s, p + 1, q)
                    s[i], s[p] = s[p], s[i]
        perm(nums, 0, len(nums) - 1)
        res = list(self.res)
        return res

